package com.klun.likou;

import static java.lang.Math.max;

public class Solution4 {

	public static void main(String[] args) {
		// 生成随机不重复数组
		// int[] prices = GenUtil.genIntArrDiff(5, 1, 2000);
		int[] prices = {1, 2, 3, 4, 5, 4, 3, 2, 1, 3};
		int i = maxProfit(prices);
		System.out.println(i);
	}

	/**
	 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
	 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
	 * 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
	 *
	 * @param prices
	 * @return
	 */
	public static int maxProfit(int[] prices) {
		if (prices.length == 0) return 0;
		int s1 = -prices[0], s2 = Integer.MIN_VALUE, s3 = Integer.MIN_VALUE, s4 = Integer.MIN_VALUE;
		for (int i = 1; i < prices.length; ++i) {
			s1 = max(s1, -prices[i]);    //买入价格更低的股
			s2 = max(s2, s1 + prices[i]);//卖出当前股，或者不操作
			s3 = max(s3, s2 - prices[i]);//第二次买入，或者不操作
			s4 = max(s4, s3 + prices[i]);//第二次卖出，或者不操作
		}
		return max(0, s4);
	}

	/**
	 * 状态转移
	 *
	 * @param prices
	 * @return
	 */
	public int maxProfit2(int[] prices) {
		if (prices.length == 0) {
			return 0;
		}
		int dp1 = 0;
		int dp2 = 0;
		int min1 = prices[0];
		int min2 = prices[0];
		for (int i = 1; i < prices.length; i++) {
			min1 = Math.min(prices[i] - 0, min1);
			dp1 = Math.max(dp1, prices[i] - min1);

			min2 = Math.min(prices[i] - dp1, min2);
			dp2 = Math.max(dp2, prices[i] - min2);
		}
		return dp2;
	}
}
